package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author： pang-yun
 * @date： 2021-11-12 17:11
 * 功能目的 ：用于  邻接矩阵 实现 图
 */

public class FirstGraph {
    public static void main(String[] args) {
        String[] vertexValues = {"A", "B", "C", "D", "E"};
        Graph graph = new Graph(5);
        Arrays.asList(vertexValues).stream().forEach(x -> graph.insertVertex(x));  // 放入 五个顶点
        // 连接边
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);

        graph.showGraph();

        System.out.println("深度遍历 : ");
//        graph.depthFirstSearch();


        System.out.println("广度优先: ");
        graph.widthFirstSearch();
    }
}

class Graph {
    /**
     * 存放顶点的 集合
     */
    private ArrayList<String> vertexList;
    /**
     * 表示边的 邻接矩阵
     */
    private int[][] edges;
    /**
     * edges  边的数目
     */
    private int numOfEdges;
    /**
     * 深度优先 depth of search   dfs  用于记录节点是否被访问
     */
    private boolean[] isVisited;

    public Graph(int vertexNum) {
        this.vertexList = new ArrayList<>(vertexNum);
        this.edges = new int[vertexNum][vertexNum];
        this.numOfEdges = 0;
        this.isVisited = new boolean[vertexNum];
    }

    // 插入节点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    // 添加边

    /**
     * @param vertexA 对应点的下标 即对应第几个顶点
     * @param vertexB 对应的第二个顶点
     * @param weight  是否连接  0  没有连接   1 连接
     */
    public void insertEdge(int vertexA, int vertexB, int weight) {
        edges[vertexA][vertexB] = weight;
        edges[vertexA][vertexB] = weight;
        numOfEdges++;
    }

    //------------------图中常用的方法-------
    //返回节点的个数
    public int getNumOfVertexes() {
        return vertexList.size();
    }

    // 返回边的数目
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 返回 节点 i 对应的数据
    public String getValueByIndex(int index) {
        return vertexList.get(index);
    }

    // 返回 vertexA vertexB 两者的权值
    public int getVertexesWeight(int indexA, int indexB) {
        return edges[indexA][indexB];
    }

    // 显示图
    public void showGraph() {
        for (int[] array : edges) {
            System.out.println(Arrays.toString(array));
        }
    }


    //------------用于 dfs  -----

    /**
     * 得到第一个邻接节点的下标
     *
     * @param index 节点坐标
     * @return -1 代表 没有 邻接节点    j 代表下一个相连的节点坐标
     */
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexList.size(); j++) {
            if (edges[index][j] == 1) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标 找到下一个 邻接节点
     *
     * @param vertexA 寻找与 A 相连的点
     * @param vertexB 原与A 相连的点
     * @return 新的节点坐标   -1 则代表无
     */
    public int getNextNeighbor(int vertexA, int vertexB) {
        for (int i = vertexB + 1; i < vertexList.size(); i++) {
            if (edges[vertexA][i] == 1) {
                return i;
            }
        }
        return -1;
    }


    // 全部顶点进行 dfs
    public void depthFirstSearch() {
        // 遍历所有节点 进行dfs
        for (int i = 0; i < getNumOfVertexes(); i++) {
            if (!isVisited[i]) {
                depthFirstSearch(isVisited, i);
            }
        }
    }

    // dfs  单个顶点 深度优先
    public void depthFirstSearch(boolean[] isVisited, int i) {
        // 首先访问该节点  输出
        System.out.print(getValueByIndex(i) + "->");
        // 将节点设置成为 访问
        isVisited[i] = true;
        // 查找 节点的 第一个邻接节点
        int firstNeighbor = getFirstNeighbor(i);
        // 说明有邻接节点
        while (firstNeighbor != -1) {
            // 是否访问过
            if (!isVisited[firstNeighbor]) {
                depthFirstSearch(isVisited, firstNeighbor);
            }
            // 如果节点已经被访问过
            firstNeighbor = getNextNeighbor(i, firstNeighbor);

        }
    }

    // 对全部顶点做广度优先
    public void widthFirstSearch(){
        // 遍历所有节点 进行dfs
        for (int i = 0; i < getNumOfVertexes(); i++) {
            if (!isVisited[i]) {
                widthFirstSearch(isVisited, i);
            }
        }
    }

    // wfs  广度 优先
    public void widthFirstSearch(boolean[] isVisited, int i) {
        //头结点 对应下标
        int u;
        // 临接节点对应下标
        int w;

        // LinkList 有 removeLast removeFirst 可以作为 队列使用  记录节点的访问顺序
        LinkedList<Integer> queue = new LinkedList();

        // 访问节点的信息
        System.out.print(getValueByIndex(i) + " => ");

        //访问节点已经访问
        isVisited[i] = true;

        // 将节点加入队列
        queue.addLast(i);

        while (!queue.isEmpty()) {
            //取出 队列的头结点下标
            u = queue.removeFirst();
            //得到第一个邻接节点
            w = getFirstNeighbor(u);

            // 找到邻接节点之后
            while (w != -1) {
                // 查看是否访问过
                if (!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + " => ");
                    // 标记为已经访问
                    isVisited[w] = true;
                    //入队
                    queue.addLast(w);
                }
                //以u 为前驱点， 找到 w后面的下一个邻接节点
                w = getNextNeighbor(u, w);
            }
        }
    }

}
